Identifier-Based Encryption (IBE) is an emerging cryptographic schema. A number of IBE cryptographic methods are known, including:                methods based on “Quadratic Residuosity” as described in the paper: “An identity based encryption scheme based on quadratic residues”, C. Cocks, Proceedings of the 8th IMA International Conference on Cryptography and Coding, LNCS 2260, pp 360-363, Springer-Verlag, 2001;        methods using Weil or Tate pairings—see, for example: D. Boneh, M. Franklin—“Identity-based Encryption from the Weil Pairing” in Advances in Cryptology —CRYPTO 2001, LNCS 2139, pp. 213-229, Springer-Verlag, 2001;        methods based on mediated RSA as described in the paper “Identity based encryption using mediated RSA”, D. Boneh, X. Ding and G. Tsudik, 3rd Workshop on Information Security Application, Jeju Island, Korea, August, 2002.        
As the present invention also uses RSA cryptography, a description of the above-referenced identifier-based mediated RSA method is given below after a brief review of a basic RSA implementation and a mediated RSA arrangement.
The RSA public key cryptographic method is well known and in its basic form is a two-party method in which a first party generates a public/private key pair and a second party uses the first party's public key to encrypt messages for sending to the first party, the latter then using its private key to decrypt the messages. More particularly, and with reference to FIG. 1 of the accompanying drawings, in the basic RSA encryption method the following operational steps are carried out by a message sender A and a message recipient B acting through respective computing entities 10 and 20:
Initial Set Up Phase
                1. B chooses distinct random primes p and q.        2. B computes n=(p).(q) and φ=(p−1).(q−1).        3. B selects an encryption exponent e such that e and φ have no common factors.        4. B computes a decryption exponent d=1/e mod φ        5. B publishes both e and n as its public key and keeps d secret as its private key (p and q are either destroyed or also kept secret)Message Transfer Phase        6. A generates a message m.        7. A computes me mod n and sends this to B.        8. B computes (me)d mod n to recover m.        
The set up phase is carried out once whilst the message transfer phase is carried out for each message to be sent from A to B. In practice, the set up phase may be carried out on behalf of B by a certificate authority that provides a trustable certificate associating B to its public key <e,n> and communicates d securely to B; the value of e is fixed for any particular domain.
It is often required to provide for control of message sending from A to B using a particular key pair. For example, A and B may initially be members of the same organization with A sending messages to B using a public key for B that was certified or otherwise vouched for by the organization as being associated with B; however, should B leave the organization, it is desirable that the validity of B's public key be immediately revoked. One way of doing this is by the use of a revocation list that A must check each time it wants to send a message. A more reliable method is to use a mediated RSA method in which the decryption exponent d is split into two components, one held by B and the other held by a security mediator; in this case, both decryption exponent components must be applied to an encrypted message to decrypt it. This means that the security mediator must be contacted by B each time B wishes to decrypt a new encrypted message from A; the security mediator thus has control over which messages B decrypts and can therefore implement any desired control policy including, in the present example, preventing B decrypting messages after B has left the organization.
However, it will generally be undesirable for the security mediator to have the ability to fully decrypt messages sent to B which implies that the security mediator must not have knowledge of B's decryption exponent component (or the data needed to compute it). Therefore, the security mediator must be separate from the entity generating the two decryption exponent components; since this latter entity clearly cannot be B (as B would then not need to go to the security mediator to decrypt a message), a separate key generation entity is needed with the result that most mediated RSA methods are four-party methods.
Inherent positive features of mediated RSA methods are that the messages passing between B and the security mediator are encrypted, and that the intended recipient is the only recipient capable of reading a message even if the security mediator is misled as to the identity of the recipient passing it the message. An inherent drawback of mediated RSA methods is that, notwithstanding the separation of the KGC and the security mediator which should ensure that messages to B cannot be read by the security mediator, so far as B is concerned there is no real guarantee that the KGC and the security mediator are not collaborating to read B's messages.
Considering now the identifier-based mediated RSA method described in the above-referenced paper by Boneh, Ding and Tsudik, this differs from normal mediated RSA methods in that it is the encryption exponent e that is made recipient specific rather than the values of n and d. More particularly, each potential recipient B has an associated predetermined identifier string IDB, such as an email address, that identifies the recipient. Thus, there exists a set of predetermined identifier strings IDB which by their nature are generally known to A and to the key generation center KGC. When A wishes to send a message to a particular recipient B, A chooses the relevant identifier string from the set of such strings and uses the chosen string to compute an encryption exponent. To effect its partial decrypt of the message, the security mediator SEM uses a decryption exponent component that the KGC has pre-computed for the recipient concerned using the known identifier string IDB of that recipient.
FIG. 2 of the accompanying drawings depicts in more detail the operational steps carried out in the identifier-based mediated RSA method, the parties involved being a message sender A, a message recipient B, a security mediator SEM and a key generation center KGC each acting through a respective computing entity 10, 20, 30 and 40. The operational steps involved are:
Initial Set Up Phase
                1. KGC chooses distinct random primes p and q. The primes p and q are specific to a particular domain and are not recipient dependent.        2. KGC computes n=(p).(q) where n has a fixed value for the domain, this value being published in an appropriate certificate.         The KGC also computes φ=(p−1).(q−1).        For each B, the KGC carries out steps 3 to 8        3. KGC uses the identifier string IDB of the particular recipient B concerned to compute a recipient-specific encryption exponent eB; the function used to compute eB is typically a hash function. The exponent e and the value φ should have no common factors.        4. KGC computes a recipient-specific decryption exponent d=1/eB mod φ.        5. KGC chooses dU (different for each B).        6. KGC computes a recipient-specific dT=(d−dU) mod φ.        7. KGC securely communicates dT to the security mediator SEM and dU to B.        8. KGC publishes IDB for B (only if not already known to message senders—where IDB is B's email address, it typically would not be re-published by the KGC).Message Transfer Phase        9. A generates a message m.        10. A chooses the identifier string IDB of the intended recipient and computes the corresponding encryption exponent eB using the same function as used by the KGC (this function will have typically been incorporated in software provided to A's computing entity 10 for implementing the cryptographic method, but may be provided to A in any suitable manner including by distribution with n).        11. A computes meB mod n and sends this to B which forwards it to the security mediator SEM.        12. SEM computes x=(meB)dT mod n and returns it to B.        13. B receives x which is equivalent to (meB)(d−dU) mod n.        14. B computes xdU mod n to recover the message m.        
B's decryption exponent component dU can, of course, be generated by B, or jointly by the KGC and B, provided both know its value (in other words dU is a shared secret of B and the KGC). As with normal mediated RSA methods, unless the security mediator SEM only serves one recipient B, the security mediator will need to be provided with a recipient identifier in order to able to select which dT to use in step 11. This recipient identifier can be the IDB used by the sender and passed on by B or another identifier provided by B; as already indicated, it is not necessary for the security mediator to trust the recipient identifier—if the identifier does not identify the intended recipient of the message, then the message will not be even partially decrypted by application of the dT retrieved using the identifier.
Like normal mediated RSA methods, the identifier-based mediated RSA method of FIG. 2 must keep the key generation center KGC independent of the security mediator if the latter is not to have access to the messages. As a result, the identifier strings used by A must generally be predetermined strings for which the KGC has already determined the corresponding decryption exponent component dT to be used by the security mediator (the alternative of re-involving the KGC for each message to compute the dT for use by the security mediator is unattractive in practical terms).
It should also be noted that the same message m must never be encrypted using two different encryption exponents as this would compromise the security of the method. As a consequence, the basic message data must normally be combined with random padding to form the message m to be sent.
It is an object of the present invention to provide simplified identifier-based RSA cryptographic methods and systems.